package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/24 11:24
 * @description <p>包含所有字符的最短字符串</p>
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：输入两个字符串 s 和 t，请找出字符串 s 中包含字符串 t 的所有
 * 字符的最短子字符串。例如，输入的字符串 s 为"ADDBANCAD"，字符串 t 为
 * "ABC"，则字符串 s 中包含字符'A'、'B'和'C'的最短子字符串是"BANC"。如
 * 果不存在符合条件的子字符串，则返回空字符串""。如果存在多个符合条件
 * 的子字符串，则返回任意一个。
 */
public class toOffer3_2_17NO {
    public static void main(String[] args) {
        String l = "aaabbbbbcdd";
        String s = "abcdd";
        System.out.println(minWindow(l, s));
    }

    /**
     *
     * @param l
     * @param s
     * @return
     */
    public static String minWindow(String l, String s) {
        //判空
        if (l.length() < s.length()) {
            return "";
        }

        int slow = 0;
        int fast = 0;
        int min = 0;
        int max = 0;
        int result = Integer.MAX_VALUE;

        Map<Character, Integer> map = new HashMap<>();

        //扫描s字符串，把里面的所有字符串都添加到map里
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        int count = map.size();

        //扫描l字符串
       while (fast < l.length() || (count == 0 && fast == l.length())){
            //count>0说明s里的字母没找全
            if (count > 0) {
                char end = l.charAt(fast);
                if (map.containsKey(end)) {
                    map.put(end, map.get(end) - 1);
                    if (map.get(end) == 0) {
                        count--;
                    }
                }
                fast++;
            } else {
                //找全了子串，找最小子串
                if (result > fast - slow) {
                    min = slow;
                    max = fast;
                    result = max - min;
                }
                char start = l.charAt(slow);
                if (map.containsKey(start)) {
                    map.put(start, map.get(start) + 1);
                    if (map.get(start) != 0) {
                        count++;
                    }
                }
                slow++;

            }

        }
        return result < Integer.MAX_VALUE ? l.substring(min, max) : "";
    }
}